/// https://leetcode-cn.com/problems/remove-element/
pub struct Solution;

impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        let mut slow: usize = 0;
        let mut cursor: usize = 0;

        while cursor < nums.len() {
            if nums[cursor] != val {
                nums[slow] = nums[cursor];
                slow += 1;
            }
            cursor += 1;
        }
        slow as i32
    }

    pub fn left_right(nums: &mut Vec<i32>, val: i32) -> i32 {
        let mut left: usize = 0;
        let mut right: usize = nums.len();

        while left < right {
            if nums[left] != val {
                left += 1;
            } else {
                nums[left] = nums[right - 1];
                right -= 1;
            }
        }
        left as i32
    }

    pub fn left_right_complex(nums: &mut Vec<i32>, val: i32) -> i32 {
        if nums.is_empty() {
            return 0;
        }

        let mut left: usize = 0;
        let mut right: usize = nums.len() - 1;

        while left <= right {
            if nums[left] != val {
                left += 1;
            } else {
                if nums[right] != val {
                    nums[left] = nums[right];
                    right -= 1;
                    left += 1;
                } else {
                    if right == 0 {
                        break;
                    }
                    right -= 1;
                }
            }
        }
        left as i32
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn assert<F>(f: F)
        where F: Fn(&mut Vec<i32>, i32) -> i32 {
        let mut nums = vec![0, 1, 2, 2, 3, 0, 4, 2];
        assert_eq!(f(&mut nums, 2), 5);
        // assert_eq!(nums[..5], [0, 1, 4, 0, 3]);

        let mut nums = vec![3, 2, 2, 3];
        assert_eq!(f(&mut nums, 3), 2);
        assert_eq!(nums[..2], [2, 2]);

        let mut nums = vec![];
        assert_eq!(f(&mut nums, 0), 0);

        let mut nums = vec![1];
        assert_eq!(f(&mut nums, 1), 0);
    }

    bench!(assert Solution::remove_element);
    bench!(assert Solution::left_right);
    bench!(assert Solution::left_right_complex);
}
